class Solution {
public:
    long long f[20], s[20], ten[20];
    int c[20];
    int count_length(int n) {
        if (n == 0) return 1;
        int l = 0;
        while (n != 0) {
            l ++;
            c[l] = n % 10;
            n = n / 10;
        }
        return l;
    }
    int countDigitOne(int n) {
        f[1] = 1;
        s[1] = f[1];
        ten[0] = 1;
        ten[1] = 10;
        for (int i = 2; i <= 10; i ++) {
            ten[i] = ten[i-1] * 10;
            f[i] = 9 * s[i-1] + ten[i-1];
            s[i] = s[i-1] + f[i];
        }
        int l = count_length(n);
        long long ans = s[l-1];
        int t = 0;
        for (int i = l; i >= 1; i --) {
            for (int j = 0; j <= c[i]; j ++) {
                if (i == l && j == 0) continue;
                if (i != 1 && j == c[i]) continue;
                if (j == 1) ans = ans + s[i-1] + (t + 1) * ten[i-1];
                else ans = ans + s[i-1] + t * ten[i-1];
            }
            if (c[i] == 1) t = t + 1;
        }
        return (int) ans;
    }
};


/*
首先，先要求出一个s函数
s是f函数的总和，即s(x)=f(1)+f(2)+...+f(x)
f函数的定义是，长度x的自然数（不包括前导0）中，一共有多少个1
显然f(1)=1
可推导f(x)=8*s(x-1)+s(x-1)+10^(x-1)=9*s(x-1)+10^(x-1)
通过一个例子来解释f(x)的推导公式
比如说已经求得了f(4)了，现在要求f(5)
x形如ABBBB
其中A:{1,2,...,9}，B:{0,1,...,9}，A不可以为0
起初f(5)=0
当A=2时，f(5)=f(5)+f(4)
当A=3时，f(5)=f(5)+f(4)
...
当A=9时，f(5)=f(5)+f(4)
所以f(x)=8*f(x)
当A=1时，f(5)=f(5)+f(4)+10^4
因此f(x)=8*s(x-1)+s(x-1)+10^(x-1)=9*s(x-1)+10^(x-1)

这样子，假设l是数字X的长度
ans = s(l) 是答案的一部分了
还剩下长度为n且小于等于X的数字中1的个数了

最后，简单说一下「求长度为l且小于等于X的数字中1的个数」思路
比如说51321
我已经求出了{1,2,...,9999}的答案了
我还需要计算{10000,10001,...,51321}的答案
这里假设一个t，t表示历史及当前1出现的次数(从高位到低位循环时)
{10000,10001,...,19999}可以一并算出来，即 ans = ans + s(4) + 1 * 10^4，此时 t = 1，因为当前位是1
{20000,20001,...,29999}可以一并算出来，即 ans = ans + s(4) + 0 * 10^4，此时 t = 0
{30000,30001,...,39999}可以一并算出来，即 ans = ans + s(4) + 0 * 10^4，此时 t = 0
{40000,40001,...,49999}可以一并算出来，即 ans = ans + s(4) + 0 * 10^4，此时 t = 0
还差{50000,50001,...,51321}
{50000,50001,...,50999}可以一并算出来，即 ans = ans + s(3) + 0 * 10^3，此时 t = 0
由于第二个数是1，则 t = t + 1 = 1
还差{51000,51001,...,51321}
{51000,51001,...,51099}可以一并算出来，即 ans = ans + s(2) + 1 * 10^2，此时 t = 1，因为第二个数是1，t加了个1
{51100,51101,...,51199}可以一并算出来，即 ans = ans + s(2) + 2 * 10^2，此时 t = 2，当前位是1
{51200,51201,...,51299}可以一并算出来，即 ans = ans + s(2) + 1 * 10^2，此时 t = 1
还差{51300,51301,...,51321}
用同样方法可以把后面的都推导出来了，上面这段例子建议结合代码来看
*/
